import numpy as np


class Task12:
    def run(self, matrix, string):
        if len(string) == 0:
            return True

        visited = np.zeros(matrix.shape)
        for i in range(matrix.shape[0]):
            for j in range(matrix.shape[1]):
                if self.find_path(matrix, visited, i, j, string, 0):
                    return True
        return False

    def find_path(self, matrix, visited, row, col, string, string_index):
        if row < 0 or row >= matrix.shape[0] or col < 0 or col >= matrix.shape[1] or visited[row][col]:
            return False
        if matrix[row][col] == string[string_index]:
            visited[row][col] = 1
            if string_index == len(string) - 1:
                return True
            else:
                result = self.find_path(matrix, visited, row + 1, col, string, string_index + 1) \
                    or self.find_path(matrix, visited, row, col + 1, string, string_index + 1) \
                    or self.find_path(matrix, visited, row - 1, col, string, string_index + 1) \
                    or self.find_path(matrix, visited, row, col - 1, string, string_index + 1)
                if result is False:
                    visited[row][col] = 0
                return result
        else:
            return False
